Write a program that
operates with a big number of deques. Deque is a “queue with two ends”.
Input.
The first line contains the number of operations n (0 ≤ n ≤ 150000)
to operate. Each of the next n lines
gives the operation description:
·
pushfront A B – insert the number B into the front of
the deque A;
·
pushback A B – insert the number B into the end of the
deque A;
·
popfront A – delete the first element of the deque A;
·
popback A – delete the last element of the deque A.
For each operation the
parameters A and B are integers in the range from 1 to 150000
inclusive.
Output. For each command popfront or popback delete the
corresponding number. It is guaranteed that before each delete operation the
corresponding deque is not empty.
|
Sample input |
Sample output |
|
9 pushfront
1 71819 pushback
2 71820 pushback
1 1 popfront
1 popfront
1 pushfront
2 10 pushback
2 11 popback
2 popback
2 |
71819 1 11 71820 |
SOLUTION
deque
Since parameter
A is no more than 150000, there will be no more than 150000 deques. Let's
declare an array of 150000 deque structures. Then simulate the deques operations.
Declare the array of deques.
deque<int> q[150001];
Read the
number of operations n.
cin >>
n;
while (n--)
{
Read and
process the current operation.
cin >> s >> a;
if (s == "pushback")
{
cin >> b;
q[a].push_back(b);
}
if (s == "pushfront")
{
cin >> b;
q[a].push_front(b);
}
if (s == "popfront")
{
cout << q[a].front() << endl;
q[a].pop_front();
}
if (s == "popback")
{
cout << q[a].back() << endl;
q[a].pop_back();
}
}
Implement
the class deque.
class deque
{
private:
struct node
{
int data;
node *next, *prev;
node()
{
prev = next = NULL;
}
node(int a)
{
data = a;
prev = next = NULL;
}
} *Head, *Tail;
public:
deque()
{
Head = Tail = NULL;
}
void push_back(int a)
{
node *p = new node(a);
if(Head == NULL)
Head = Tail = p;
else
{
p->prev = Tail;
p->next = NULL;
Tail->next = p;
Tail = p;
}
}
void push_front(int
a)
{
node *p = new node(a);
if(Head == NULL)
Head = Tail = p;
else
{
p->next = Head;
p->prev = NULL;
Head->prev = p;
Head = p;
}
}
int pop_front(void)
{
node *p = Head;
int r = Head->data;
if(Head == Tail)
Head = Tail = NULL;
else
{
Head = Head->next;
Head->prev = NULL;
}
delete p;
return r;
}
int pop_back(void)
{
node *p = Tail;
int r = Tail->data;
if(Head == Tail)
Head = Tail = NULL;
else
{
Tail = Tail->prev;
Tail->next = NULL;
}
delete p;
return r;
}
int empty(void)
{
return Head == NULL;
}
int front(void)
{
return Head->data;
}
int back(void)
{
return Tail->data;
}
};
Declare
the array of classes deque.
#define MAX 150001
deque q[MAX];
The main part of the program. Read the input
data and simulate the deques.
scanf("%d\n",&n);
while(n--)
{
scanf("%s %d",s,&a);
if(!strcmp(s,"pushback"))
{
scanf("%d\n",&b);
q[a].push_back(b);
}
if(!strcmp(s,"pushfront"))
{
scanf("%d\n",&b);
q[a].push_front(b);
}
if(!strcmp(s,"popfront"))
{
scanf("\n");
printf("%d\n",q[a].front());
q[a].pop_front() ;
}
if(!strcmp(s,"popback"))
{
scanf("\n");
printf("%d\n",q[a].back());
q[a].pop_back();
}
}
import java.util.*;
public class Main
{
static Deque<Integer> q[];
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
q = new LinkedList[150001];
for(int i = 0; i < 150001;
i++)
q[i] = new LinkedList<Integer>();
int n = con.nextInt();
while (n-- > 0)
{
String s = con.next();
int a = con.nextInt();
if (s.equals("pushback"))
{
int b = con.nextInt();
q[a].addLast(b);
}
if (s.equals("pushfront"))
{
int b = con.nextInt();
q[a].addFirst(b);
}
if (s.equals("popback"))
{
System.out.println(q[a].removeLast());
}
if (s.equals("popfront"))
{
System.out.println(q[a].removeFirst());
}
}
con.close();
}
}